package com.huawei.tree.huffman_tree;

import java.util.ArrayList;
import java.util.Collections;

//霍夫曼树
public class HuffmanTree {
    public static Node createHuffmanTree(int[] array) {
        //1、为了排序方便，遍历数组，将array每一个元素构成一个Node，将Node放入到ArrayList中
        ArrayList<Node> nodes = new ArrayList<>();
        for (int value : array) {
            nodes.add(new Node(value));
        }

        while (nodes.size() > 1) {
            //2、排序 从小到大
            Collections.sort(nodes);

            //3、构建一棵新的二叉树
            //取出权值最小的节点
            Node leftNode = nodes.get(0);
            //取出权值第二小的节点
            Node rightNode = nodes.get(1);
            //构建新的二叉树
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.setLeft(leftNode);
            parent.setRight(rightNode);
            //删除处理过的节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //添加新节点到数组
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}
